package com.yangli.leecode.mashib;

import java.util.Stack;

/**
 * @Description 反转栈且不适用额外空间
 * @Author liyang
 * @Date 2023/1/9 16:06
 */
public class ReverseStack {
    public static void main(String[] args){
        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);
        stack.add(5);
        System.out.println(stack);
        reverse(stack);
        System.out.println(stack);
    }

    public static void reverse(Stack stack){
        if(stack.empty()){
            return;
        }else {
            int last = f(stack);
            reverse(stack);
            stack.push(last);
        }

    }

    //反转栈进行递归是每次都要获取栈底元素==>这个函数就是返回栈底并把栈底弹出，但是其他元素位置不变
    public static int f(Stack stack){
        int res = (int) stack.pop();
        if (stack.empty()) {
            return res;
        } else {
            int last = f(stack);
            stack.push(res);
            return last;
        }
    }
}
